package org.example;

public class Test1 {
    public int longestPalindromeSubseq(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        //dp[i][j]表示i-j之间的子串的最长回文子序列的长度
        int[][] dp = new int[n+1][n+1];
        //初始化，对角线的位置，也就是一个字符也是回文子序列
        for (int i = 1; i <= n; i++) dp[i][i] = 1;
        for (int j = 1; j <= n; j++) {
            for (int i = j-1; i >= 1; i--) {
                if (arr[i-1] == arr[j-1]) {
                    dp[i][j] = i + 1 == j ? 2 : dp[i+1][j-1] + 2;
                }else {
                    //当arr[i-1]!=arr[j-1]的时候，说明在i~j之间的最长回文子串的第一个和最后一个字符一定不是arr[i-1]和arr[j-1]，
                    //那么可能的最长回文子序列的第一个和最后一个字符就是arr[i]和arr[j-1]以及arr[i-1]和arr[j-2]，
                    // 那么dp[i][j]就取这两种情况的最大值
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        test1.longestPalindromeSubseq("bbbab");
        System.out.println(666);
    }
}
